package pers.qianyu.month_202012.date_20201223;

/**
 * 并查集接口
 *
 * @author mizzle rain
 * @date 2020年12月23日14:22:31
 */
interface UF {
    /* 将 p 和 q 连接 */
    void union(int p, int q);

    /* 判断 p 和 q 是否连通 */
    boolean connected(int p, int q);

    /* 返回图中有多少个连通分量 */
    int count();
}

/**
 * 并查集实现
 *
 * @author mizzle rain
 * @date 2020年12月23日14:26:04
 */
class UFImpl implements UF {
    // 连通分量
    private int count;
    // i 的父节点为 parent[i]
    private int[] parent;
    // 每个树的长度
    private int[] size;

    public UFImpl(int count) {
        this.count = count;
        this.parent = new int[count];
        this.size = new int[count];
        // 元素的父节点指向自己
        for (int i = 0; i < count; i++) {
            this.parent[i] = i;
            this.size[i] = 1;
        }
    }

    @Override
    public void union(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) {
            return;
        }

        // 那个树低，就把哪个树作为子树
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }

    // 返回某个节点的根节点
    private int findRoot(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    @Override
    public boolean connected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    @Override
    public int count() {
        return count;
    }
}